import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * Date: 2024-02-20
 * Time:10:33
 */
public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] arr1 = new int[n];
        arr1[0] = 1;
        int[] arr2 = new int[n];
        arr2[n-1] = 1;
        for(int i = 1;i < n;i++) arr1[i] = arr1[i-1] * nums[i-1];
        for(int i = n-2;i >=0;i--) arr2[i] = arr2[i+1] * nums[i+1];

        int[] ret = new int[n];
        for(int i = 0;i < n;i++) ret[i] = arr1[i] * arr2[i];
        return ret;
    }
    //////////////////////////////////////////
    //无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        HashMap<Character,Integer> map = new HashMap<>();

        int left = 0,right = 0;
        for(;right < s.length();right++) {
            char ch = s.charAt(right);
            if(!map.containsKey(ch)) map.put(ch,right);  //如果哈希表中没有出现过这个字符，那就把它加进去
            else {  //遇到重复字符
                int last = map.get(ch); //该重复字符上一次出现的位置
                left = Math.max(left,last + 1);  //最关键的一步
                map.put(ch,right);  //更新 ch 最后一次出现的下标
            }
            maxLen = Math.max(maxLen,right-left+1);
        }
        return maxLen;
    }
    ///////////////////////////////////////////////
    public static int maximumUniqueSubarray(int[] nums) {
        int max = 0;
        HashMap<Integer,Integer> map = new HashMap<>();  //数字、下标

        int left = 0,sum = 0;
        for(int right = 0;right < nums.length;right++) {
            sum += nums[right];
            if(!map.containsKey(nums[right])) map.put(nums[right],right);
            else {
                int tmp = left;
                left = Math.max(left,map.get(nums[right])+1);
                for(int i = tmp;i < left;i++) sum -= nums[i];
                map.put(nums[right],right);
            }
            max = Math.max(max,sum);
        }
        return max;
    }
    ////////////////////////////////////////////
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int[] arr1 = new int[26];  //s 子串的词频
        int[] arr2 = new int[26];  //p 的词频
        int len1 = arr1.length,len2 = arr2.length;
        for (int i = 0;i < p.length();i++) arr2[p.charAt(i) - 'a']++;
        int left = 0;
        for(int right = 0;right < s.length();right++) {
            arr1[s.charAt(right) - 'a']++;
            if(check(arr1,arr2)) ret.add(left);
            while(right - left + 1 >= p.length()) {
                arr1[s.charAt(left) - 'a']--;
                left++;
            }

        }
        return ret;
    }

    public static boolean check(int[] arr1,int[] arr2) {
        for(int i = 0;i < arr1.length;i++) {
            if(arr1[i] != arr2[i]) return false;
        }
        return true;
    }

    //////////////////////////////////////////

    //水果成篮
    public static int totalFruit(int[] fruits) {
        int max = 0;

        int left = 0,right = 0;
        int n = fruits.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(;right < n;right++) {
            map.put(fruits[right],map.getOrDefault(fruits[right],0)+1);
            System.out.println("[" + left + "," + right + "]"+ " " + map.size());
            while(map.size() > 2) {
                map.put(fruits[left],map.get(fruits[left])-1);
                if(map.get(fruits[left]) == 0) map.remove(fruits[left]);
                left++;
            }
            max = Math.max(max,right-left+1);
        }
        return max;


    }




}
